#include<iostream>
#include<vector>

using namespace std;



//floodfill05:太平洋大西洋水流问题
class Solution5 {
    vector<vector<int>> ret;
    int m;
    int n;
    int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    bool check[200][200]={};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        m=heights.size();
        n=heights[0].size();
        //cout<<m<<":"<<n<<" ";
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(dfspac(heights,i,j)&&dfsatl(heights,i,j))
                {
                    ret.push_back({i,j});
                }
            }
        }
        return ret;
    }

    bool dfspac(vector<vector<int>>& heights,int i,int j)
    {
        if(i==0||j==0)  return true;
        check[i][j]=true;
        for(auto& it:dirs)
        {
            int x=it[0]+i;
            int y=it[1]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&heights[x][y]<=heights[i][j]&&check[x][y]==false)
            {
                if(dfspac(heights,x,y))
                {
                    check[i][j]=false;return true;
                }
                    
            }                
        }
        check[i][j]=false;
        return false;
    }

    bool dfsatl(vector<vector<int>>& heights,int i,int j)
    {
        if(i==m-1||j==n-1)  return true;
        check[i][j]=true;
        for(auto& it:dirs)
        {
            int x=it[0]+i;
            int y=it[1]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&heights[x][y]<=heights[i][j]&&check[x][y]==false)
            {
                if(dfsatl(heights,x,y))
                {
                    check[i][j]=false;return true;
                }
            }                
        }
        check[i][j]=false;
        return false;
    }
};



//floodfill06:扫雷游戏
class Solution6 {
public:
    //vector<vector<char>> ret;
    int m;int n;
    //int digui=0;
    int dirs[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
    {
        m=board.size();
        n=board[0].size();
        for(int i=0;i<click.size();i+=2)
        {
            if(board[click[i]][click[i+1]]=='M')
            {
                board[click[i]][click[i+1]]='X';
                return board;
            }
            else dfs(board,click[i],click[i+1]);
        }
        return board;    
    }
    void dfs(vector<vector<char>>& board,int i,int j)
    {
        int count=0;
        for(auto& it:dirs)
        {
            int x=it[0]+i;int y=it[1]+j;
            //cout<<x<<":"<<y<<" ";
            if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='M')
            {
                count++;
                //cout<<digui++<<" ";
            }
        }
        if(count>0)
        {
            board[i][j]=count+'0';
            return;
        } 
        else
        {
            board[i][j]='B';
            //int count=0
            for(auto& it:dirs)
            {
                //cout<<digui++;
                int x=it[0]+i;int y=it[1]+j;
                //cout<<x<<":"<<y<<" ";
                if(x>=0&&x<m&&y>=0&&y<n&&board[x][y]=='E')
                {
                    //cout<<digui++<<" ";
                    dfs(board,x,y);
                }
            }
        }
    }
};


//floodfill07:衣柜整理
class Solution7 {
public:
    int ret=0;
    bool check[100][100]={};
    int dx[2]={0,1};
    int dy[2]={1,0};
    int m=0;int n=0;
    int wardrobeFinishing(int x, int y, int cnt) 
    {
        m=x;
        n=y;
        dfs(0,0,cnt);
        return ret;   
    }
    void dfs(int i,int j,int cnt)
    {
        check[i][j]=true;
        if(digit(i)+digit(j)>cnt)   return;
        ret++;
        for(int k=0;k<2;k++)
        {
            int x=i+dx[k];
            int y=j+dy[k];
            if(y<n&&x<m&&check[x][y]==false)
            {
                dfs(x,y,cnt);
            }
        }
    }
    int digit(int x)
    {
        int sum=0;
        while(x)
        {
            sum+=x%10;
            x/=10;
        }
        return sum;
    }
};

int main()
{
    return 0;
}